package com.leetcode.algorithm.y22.m07.w3;

import java.util.ArrayDeque;
import java.util.Deque;

import com.leetcode.algorithm.common.ListNode;

/**
 * 445. 两数相加 II
 * 
 * https://leetcode.cn/problems/add-two-numbers-ii/
 * 
 * @author jie.deng
 *
 */
class Question0445Solution01 {
	
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		Deque<Integer> stack1 = new ArrayDeque<Integer>();
		Deque<Integer> stack2 = new ArrayDeque<Integer>();
		Deque<Integer> stack = new ArrayDeque<Integer>();
		ListNode cur1 = l1;
		while (cur1 != null) {
			stack1.push(cur1.val);
			cur1 = cur1.next;
		}
		ListNode cur2 = l2;
		while (cur2 != null) {
			stack2.push(cur2.val);
			cur2 = cur2.next;
		}
		int carry = 0;
		while (!stack1.isEmpty() || !stack2.isEmpty()) {
			int i1 = 0;
			if (!stack1.isEmpty()) {
				i1 = stack1.pop().intValue();
			}
			int i2 = 0;
			if (!stack2.isEmpty()) {
				i2 = stack2.pop().intValue();
			}
			int sum = i1 + i2 + carry;
			stack.push(sum % 10);
			carry = sum / 10;
		}
		ListNode sentinel = new ListNode();
		ListNode cur = sentinel;
		if (carry == 1) {
			cur.next = new ListNode(1);
			cur = cur.next;
		}
		while (!stack.isEmpty()) {
			cur.next = new ListNode(stack.pop().intValue());
			cur = cur.next;
		}
		return sentinel.next;
	}
    
}